/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-09-09
 * Time: 10:57
 */
import java.util.*;

public class TestCode5 {
    public static void main(String[] args) {
        // 定义节点间的关系
        int[][] edges = {{1, 2}, {3, 4}, {5, 6}, {5, 2}, {7, 8}, {8, 9}};

        // 获取所有节点并建立邻接表
        Map<Integer, List<Integer>> adjacencyList = buildAdjacencyList(edges);

        // 执行分组
        List<Set<Integer>> groups = findGroups(adjacencyList);

        // 输出结果
        System.out.println("分组结果:");
        for (Set<Integer> group : groups) {
            System.out.println(group);
        }
    }

    // 构建邻接表表示图
    private static Map<Integer, List<Integer>> buildAdjacencyList(int[][] edges) {
        Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

        for (int[] edge : edges) {
            int node1 = edge[0];
            int node2 = edge[1];

            // 添加双向连接
            adjacencyList.computeIfAbsent(node1, k -> new ArrayList<>()).add(node2);
            adjacencyList.computeIfAbsent(node2, k -> new ArrayList<>()).add(node1);
        }

        return adjacencyList;
    }

    // 查找所有连通分组
    private static List<Set<Integer>> findGroups(Map<Integer, List<Integer>> adjacencyList) {
        List<Set<Integer>> groups = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();

        // 对每个未访问的节点执行DFS
        for (int node : adjacencyList.keySet()) {
            if (!visited.contains(node)) {
                Set<Integer> group = new HashSet<>();
                dfs(node, adjacencyList, visited, group);
                groups.add(group);
            }
        }

        return groups;
    }

    // 深度优先搜索
    private static void dfs(int node, Map<Integer, List<Integer>> adjacencyList,
                            Set<Integer> visited, Set<Integer> group) {
        // 标记当前节点为已访问并加入当前分组
        visited.add(node);
        group.add(node);

        // 访问所有相邻节点
        for (int neighbor : adjacencyList.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, adjacencyList, visited, group);
            }
        }
    }
}

